// https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

// 题干：家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。
//      整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。
//      整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。
//      同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。
//      请返回整理师 总共需要整理多少个格子。

// 示例：输入：m = 4, n = 7, cnt = 5
//       输出：18

// 碎语：本题可以有多种方法，我们仍然采用floodFill算法

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool vis[201][201];
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    int m, n, ret, cnt;
public:
    int wardrobeFinishing(int _m, int _n, int _cnt)
    {
        ret = 0, m = _m, n = _n, cnt = _cnt;
        memset(vis, 0, sizeof(vis));

        dfs(0,0);

        return ret;
    }

    void dfs(int i, int j)
    {
        vis[i][j] = true, ret++;
        for (int k = 0 ; k < 4 ; k++){
            int x = i + dx[k], y = j + dy[k];

            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && digit(x) + digit(y) <= cnt) dfs(x, y);
        }
    }

    int digit(int num)
    {
        int sum = 0;
        while (num){
            sum += num % 10;
            num /= 10;
        }

        return sum;
    }
};

int main()
{
    Solution sol;

    cout << sol.wardrobeFinishing(4,7,5) << endl;

    return 0;
}